package Leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class generateParenthesis {
    // 存储生成的所有合法括号组合
    List<String> result = new ArrayList<>();
    // 构建中的括号字符串
    StringBuilder path = new StringBuilder();

    /**
     * 主函数，用于生成n对括号的所有合法组合
     * @param n 指定生成括号的对数
     * @return 返回所有合法的括号组合列表
     */
    public List<String> generateParenthesis(int n) {
        // 从0对左右括号开始回溯
        back(0, 0, n);
        return result;
    }

    /**
     * 回溯函数，用于生成括号组合
     * @param left 已经使用的左括号的数量
     * @param right 已经使用的右括号的数量
     * @param n 总共需要生成的括号对数
     */
    public void back(int left, int right, int n){
        // 如果当前组合的括号数量超过最大值或左右括号数量不合法，则终止当前路径
        if (left > n || right > n || left < right){
            return;
        }
        // 如果当前构建的括号字符串达到最大长度，则将其添加到结果列表中
        if (path.length() == 2 * n){
            result.add(path.toString());
        }
        // 尝试添加一个左括号，并继续回溯
        path.append("(");
        back(left + 1, right, n);
        // 回溯，移除最后一个字符，尝试其他可能性
        path.deleteCharAt(path.length() - 1);

        // 尝试添加一个右括号，并继续回溯
        path.append(")");
        back(left, right + 1, n);
        // 回溯，移除最后一个字符，尝试其他可能性
        path.deleteCharAt(path.length() - 1);
    }
}
